package 算法;

public class 二叉搜索树的最近公共祖先 {
    public static void main(String[] args) {
        TreeNode t = new TreeNode(2);
        t.left  = new TreeNode(1);
        System.out.println(lowestCommonAncestor(t,new TreeNode(2),new TreeNode(1)).val);
    }
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(q.val < p.val){
            q.val = q.val+p.val;
            p.val = q.val - p.val;
            q.val = q.val - p.val;
        }
        if((p.val<=root.val && q.val>= root.val) || p.val == root.val || q.val == root.val) return root;

        else if(p.val <= root.val && q.val <= root.val){
            return lowestCommonAncestor(root.left,p,q);
        }else return lowestCommonAncestor(root.right,p,q);
    }
}
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }